package suanfa;

import java.util.Random;

public class findKthLargest {
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums,0,nums.length-1,k);
    }
    public int qsort(int[] nums,int l,int r,int k){
        if(l==r) return nums[l];
        //1.随机选择一个基准元素
        int key=nums[new Random().nextInt(r-l+1)+l];
        //2.根据基准元素，使数组分三块
        int left=l-1,right=r+1,i=l;
        //并没有完全排好序只是和自身进行交换
        while(i<right){
            if(nums[i]<key) swap(nums,++left,i++);
            else if(nums[i]==key) i++;
            else swap(nums,--right,i);
        }
        //3.分类讨论
        //[l,left] [left+1,right-1] [right,r]
        int b=right-left-1,c=r-right+1;
        if(c>=k) return qsort(nums,right,r,k);
        else if(b+c>=k) return key;
        else return qsort(nums,l,left,k-b-c);
    }
    public void swap(int[] nums,int left,int right){
        int t=nums[left];
        nums[left]=nums[right];
        nums[right]=t;
    }
}
